#include <stdio.h>
void choose (int *a,int  len)
{
	for(int i=0;i<len;i++)
	{
		int min=i;
		for(int j=i;j<len;j++)
		{
			if(a[j]<a[min])
				min=j;
		}
		int temp=a[i];
		a[i]=a[min];
		a[min]=temp;
	}
}
void choose2(int *a,int len)
{
	int left=0;
	int right=len-1;
	int temp;
	while(left<right)
	{
		int min=left;
		int max=right;
		for(int i=left;i<=right;i++)
		{
			if(a[i]<a[min])
				min=i;
			if(a[i]>a[max])
				max=i;
		}
		temp=a[min];
		a[min]=a[left];
		a[left]=temp;
		if(max==left)
		{
			max=min;
		}
		temp=a[max];
		a[max]=a[right];
		a[right]=temp;
		left++;
		right--;
	}
}
void insert(int *a,int len)
{
	
	for(int i=0;i<len;i++)
	{
		int temp=a[i];
		int j=i;
		for(;j>0;j--)
		{
			if(a[j-1]>temp)
				a[j]=a[j-1];
			else
				break;
		}
		a[j]=temp;
	}
}
void fast(int *a,int start,int end)
{
	int left=start;
	int right=end;
	int temp=a[start];

	while(left<right)
	{
		while(left<right&&a[right]>temp)
			right--;
		if(left<right)
		{
			a[left]=a[right];
			left++;
		}
		while(left<right&&a[left]<temp)
			left++;
		if(left<right)
		{
			a[right]=a[left];
			right--;
		}
		a[left]=temp;
		fast(a,start,left-1);
		fast(a,right+1,end);
		
	}
}
int main()
{
	int a[]={4,2,6,8,1,9};
	// choose2(a,sizeof(a)/sizeof(a[0]));
	// fast(a,0,sizeof(a)/sizeof(a[0])-1);
	insert(a,sizeof(a)/sizeof(a[0]));
	for(int i=0;i<sizeof(a)/sizeof(a[0]);i++)
		printf("%d ",a[i]);
	printf("\n");	
	return 0;
}
